#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <windows.h> // 用于高精度计时

typedef struct {
    int id;
    int weight;
    double value;
    double unit_value; // 单位价值
} Item;

// 生成随机物品数据并写入文件
void generate_data(int n, const char* filename) {
    FILE* fp = fopen(filename, "w");
    if (fp == NULL) {
        printf("无法打开文件！\n");
        return;
    }
    srand((unsigned)time(NULL));
    for (int i = 0; i < n; i++) {
        int weight = rand() % 100 + 1; // 重量: 1~100
        double value = 100.0 + (rand() % 900001) / 1000.0; // 价值: 100.00~1000.00
        fprintf(fp, "%d\t\t%d\t\t%.2f\n", i + 1, weight, value);
    }
    fclose(fp);
}

// 从文件读取物品数据
Item* read_data(int n, const char* filename) {
    FILE* fp = fopen(filename, "r");
    if (fp == NULL) {
        printf("无法打开文件！\n");
        return NULL;
    }
    Item* items = (Item*)malloc(n * sizeof(Item));
    for (int i = 0; i < n; i++) {
        fscanf(fp, "%d %d %lf", &items[i].id, &items[i].weight, &items[i].value);
        items[i].unit_value = items[i].value / items[i].weight;
    }
    fclose(fp);
    return items;
}

// 蛮力法求解（仅适用于小规模问题）
void brute_force(Item* items, int n, int capacity, double* max_value, int* selected) {
    long long total = 1LL << n; // 2^n种可能
    double best_value = 0;
    int* best_choice = (int*)calloc(n, sizeof(int));

    for (long long i = 0; i < total; i++) {
        int current_weight = 0;
        double current_value = 0.0;
        int* temp_choice = (int*)calloc(n, sizeof(int));

        for (int j = 0; j < n; j++) {
            if (i & (1LL << j)) {
                if (current_weight + items[j].weight > capacity) {
                    current_value = -1; // 标记无效
                    break;
                }
                current_weight += items[j].weight;
                current_value += items[j].value;
                temp_choice[j] = 1;
            }
        }

        if (current_value > best_value) {
            best_value = current_value;
            memcpy(best_choice, temp_choice, n * sizeof(int));
        }
        free(temp_choice);
    }

    *max_value = best_value;
    memcpy(selected, best_choice, n * sizeof(int));
    free(best_choice);
}

// 动态规划法求解
void dp_knapsack(Item* items, int n, int capacity, double* max_value, int* selected) {
    // 转换价值为整数（分）以避免浮点误差
    long long** dp = (long long**)malloc((n + 1) * sizeof(long long*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (long long*)calloc(capacity + 1, sizeof(long long));
    }

    // 动态规划填表
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (items[i - 1].weight <= w) {
                long long take = dp[i - 1][w - items[i - 1].weight] + (long long)(items[i - 1].value * 100);
                if (take > dp[i - 1][w]) {
                    dp[i][w] = take;
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 回溯找出选择的物品
    int w = capacity;
    for (int i = n; i > 0; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            selected[i - 1] = 1;
            w -= items[i - 1].weight;
        }
    }

    *max_value = dp[n][capacity] / 100.0; // 转换回元

    // 释放内存
    for (int i = 0; i <= n; i++) free(dp[i]);
    free(dp);
}

// 比较函数（用于贪心法排序）
int compare_unit_value(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    if (itemB->unit_value > itemA->unit_value) return 1;
    if (itemB->unit_value < itemA->unit_value) return -1;
    return 0;
}

// 贪心法求解
void greedy_knapsack(Item* items, int n, int capacity, double* max_value, int* selected) {
    // 创建副本以避免修改原始数据
    Item* sorted_items = (Item*)malloc(n * sizeof(Item));
    memcpy(sorted_items, items, n * sizeof(Item));

    // 按单位价值降序排序
    qsort(sorted_items, n, sizeof(Item), compare_unit_value);

    double total_value = 0.0;
    int current_weight = 0;

    // 贪心选择
    for (int i = 0; i < n; i++) {
        if (current_weight + sorted_items[i].weight <= capacity) {
            current_weight += sorted_items[i].weight;
            total_value += sorted_items[i].value;
            selected[sorted_items[i].id - 1] = 1; // 通过id映射回原位置
        }
    }

    *max_value = total_value;
    free(sorted_items);
}

// 回溯法辅助函数（带剪枝）
void backtrack(Item* items, int n, int capacity, int index, int current_weight,
             double current_value, double* best_value, int* current_selected,
             int* best_selected) {
    if (index == n) {
        if (current_value > *best_value) {
            *best_value = current_value;
            memcpy(best_selected, current_selected, n * sizeof(int));
        }
        return;
    }

    // 剪枝：计算上界（连续背包问题）
    double upper_bound = current_value;
    int remaining = capacity - current_weight;
    for (int i = index; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            upper_bound += items[i].value;
            remaining -= items[i].weight;
        } else {
            upper_bound += items[i].unit_value * remaining;
            remaining = 0;
        }
    }

    if (upper_bound <= *best_value) return; // 剪枝

    // 选择当前物品
    if (current_weight + items[index].weight <= capacity) {
        current_selected[index] = 1;
        backtrack(items, n, capacity, index + 1,
                 current_weight + items[index].weight,
                 current_value + items[index].value,
                 best_value, current_selected, best_selected);
        current_selected[index] = 0;
    }

    // 不选择当前物品
    backtrack(items, n, capacity, index + 1,
             current_weight, current_value,
             best_value, current_selected, best_selected);
}

// 回溯法求解
void backtrack_knapsack(Item* items, int n, int capacity, double* max_value, int* selected) {
    // 创建副本并排序（提高剪枝效率）
    Item* sorted_items = (Item*)malloc(n * sizeof(Item));
    memcpy(sorted_items, items, n * sizeof(Item));
    qsort(sorted_items, n, sizeof(Item), compare_unit_value);

    double best_value = 0.0;
    int* current_selected = (int*)calloc(n, sizeof(int));
    int* best_selected = (int*)calloc(n, sizeof(int));

    backtrack(sorted_items, n, capacity, 0, 0, 0.0, &best_value, current_selected, best_selected);

    // 将选择结果映射回原始ID
    for (int i = 0; i < n; i++) {
        if (best_selected[i]) {
            selected[sorted_items[i].id - 1] = 1;
        }
    }

    *max_value = best_value;
    free(sorted_items);
    free(current_selected);
    free(best_selected);
}

// 打印结果
void print_results(Item* items, int n, double max_value, int* selected, const char* method) {
    printf("\n%s法选择的物品:\n", method);
    printf("编号\t重量\t价值\n");
    printf("-------------------\n");

    int total_weight = 0;
    double total_value = 0.0;
    for (int i = 0; i < n; i++) {
        if (selected[i]) {
            printf("%d\t%d\t%.2f\n", items[i].id, items[i].weight, items[i].value);
            total_weight += items[i].weight;
            total_value += items[i].value;
        }
    }

    printf("-------------------\n");
    printf("总重量: %d\n", total_weight);
    printf("总价值: %.2f\n", total_value);
    printf("计算的最大价值: %.2f\n", max_value);
}

int main() {
    const int n = 1000;          // 物品数量
    const int capacity = 10000;   // 背包容量
    const char* filename = "thing.txt";

    // 生成数据并写入文件
    generate_data(n, filename);
    printf("已生成%d个物品数据并保存到%s\n", n, filename);

    // 从文件读取数据
    Item* items = read_data(n, filename);
    if (items == NULL) return 1;

    // 初始化选择数组
    int* selected_brute = (int*)calloc(n, sizeof(int));
    int* selected_dp = (int*)calloc(n, sizeof(int));
    int* selected_greedy = (int*)calloc(n, sizeof(int));
    int* selected_backtrack = (int*)calloc(n, sizeof(int));

    // 存储结果
    double max_value_brute = 0.0, max_value_dp = 0.0;
    double max_value_greedy = 0.0, max_value_backtrack = 0.0;

    // 高精度计时
    LARGE_INTEGER freq, start, end;
    QueryPerformanceFrequency(&freq);
    double elapsed_time;

    // 蛮力法（仅当n<=20时执行）
    if (n <= 20) {
        QueryPerformanceCounter(&start);
        brute_force(items, n, capacity, &max_value_brute, selected_brute);
        QueryPerformanceCounter(&end);
        elapsed_time = (end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
        print_results(items, n, max_value_brute, selected_brute, "蛮力");
        printf("蛮力法执行时间: %.2f ms\n", elapsed_time);
    } else {
        printf("\n蛮力法跳过（物品数量%d>20，计算量过大）\n", n);
    }

    // 动态规划法
    QueryPerformanceCounter(&start);
    dp_knapsack(items, n, capacity, &max_value_dp, selected_dp);
    QueryPerformanceCounter(&end);
    elapsed_time = (end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
    print_results(items, n, max_value_dp, selected_dp, "动态规划");
    printf("动态规划法执行时间: %.2f ms\n", elapsed_time);

    // 贪心法
    QueryPerformanceCounter(&start);
    greedy_knapsack(items, n, capacity, &max_value_greedy, selected_greedy);
    QueryPerformanceCounter(&end);
    elapsed_time = (end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
    print_results(items, n, max_value_greedy, selected_greedy, "贪心");
    printf("贪心法执行时间: %.2f ms\n", elapsed_time);

    // 回溯法
    QueryPerformanceCounter(&start);
    backtrack_knapsack(items, n, capacity, &max_value_backtrack, selected_backtrack);
    QueryPerformanceCounter(&end);
    elapsed_time = (end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
    print_results(items, n, max_value_backtrack, selected_backtrack, "回溯");
    printf("回溯法执行时间: %.2f ms\n", elapsed_time);

    // 释放内存
    free(items);
    free(selected_brute);
    free(selected_dp);
    free(selected_greedy);
    free(selected_backtrack);

    return 0;
}
